package ru.susu.algebra.ranks;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Map;

import com.google.common.collect.Maps;

/**
 * @author akargapolov
 * @since: 07.11.2009
 */
public class PartitionsCounter
{
	private static final int size = 1001;
	private static final int start = 10;

	public static void main(String[] args)
	{
		// printAllPartitions();
		// printDiffPartitions();
//		 printDiffOddPartitions();
		 printShiftPartitions();
		//print2KPartitions();
		// diffOddByDevisors();
//		printDiffDiffPartitions();
//		printDiffDiffOddPartitions();
//		ranksByFormula();
	}

	public static void printDiffPartitions()
	{
		BigInteger[] array = new BigInteger[size];
		for (int i = 0; i < size; i++)
		{
			array[i] = BigInteger.valueOf(0);
		}
		array[0] = BigInteger.valueOf(1);

		for (int i = 1; i < size; i++)
		{
			for (int j = size - i - 1; j >= 0; j--)
			{
				array[j + i] = array[j + i].add(array[j]);
			}
		}

		for (int i = start; i < size; i++)
		{
			System.out.println(i + " = " + array[i]);
		}
	}

	/**
	 * Разница между количеством разбиений (четной длины и нечетной) на различные числа
	 */
	public static void printDiffDiffPartitions()
	{
		BigInteger[] array = new BigInteger[size];
		for (int i = 0; i < size; i++)
		{
			array[i] = BigInteger.valueOf(0);
		}
		array[0] = BigInteger.valueOf(1);

		for (int i = 1; i < size; i++)
		{
			for (int j = size - i - 1; j >= 0; j--)
			{
				array[j + i] = array[j + i].subtract(array[j]);
			}
		}

		for (int i = start; i < size; i++)
		{
			BigInteger recResult = recDiffDiff(i, 1, 0);
			System.out.println(i + " = " + array[i] + " = " + recResult);
		}
	}

	private static Map<String, BigInteger> _diffDiff = Maps.newHashMap();

	public static BigInteger recDiffDiff(int n, int k, int length)
	{
		if (k > n)
		{
			if (n == 0)
			{
				return (length % 2 == 1) ? BigInteger.valueOf(-1) : BigInteger.valueOf(1);
			}
			return BigInteger.ZERO;
		}
		String key = n + "_" + k + "_" + length;
		if (_diffDiff.containsKey(key))
		{
			return _diffDiff.get(key);
		}
		BigInteger result = recDiffDiff(n, k + 1, length).add(recDiffDiff(n - k, k + 1, (length + 1)%4));
		_diffDiff.put(key, result);
		return result;
	}

	/**
	 * Разница между количеством разбиений (четной длины и нечетной) на различные числа
	 */
	public static void printDiffDiffOddPartitions()
	{
		BigInteger[] array = new BigInteger[size];
		for (int i = 0; i < size; i++)
		{
			array[i] = BigInteger.valueOf(0);
		}
		array[0] = BigInteger.valueOf(1);

		for (int i = 1; i < size; i+=2)
		{
			for (int j = size - i - 1; j >= 0; j--)
			{
				array[j + i] = array[j + i].subtract(array[j]);
			}
		}

		for (int i = start; i < size; i++)
		{
			BigInteger recResult = recDiffDiffOdd(i, 1, 0);
			System.out.println(i + " = " + array[i] + " = " + recResult + " = " + recDiffDiff(i, 1, 0));
		}
	}

	private static Map<String, BigInteger> _diffDiffOdd = Maps.newHashMap();

	public static BigInteger recDiffDiffOdd(int n, int k, int length)
	{
		if (k > n)
		{
			if (n == 0)
			{
				return (length % 4 <= 1) ? BigInteger.valueOf(-1) : BigInteger.valueOf(1);
			}
			return BigInteger.ZERO;
		}
		String key = n + "_" + k + "_" + length;
		if (_diffDiffOdd.containsKey(key))
		{
			return _diffDiffOdd.get(key);
		}
		BigInteger result = recDiffDiffOdd(n, k + 2, length).add(recDiffDiffOdd(n - k, k + 2, (length + 1)%4));
		_diffDiffOdd.put(key, result);
		return result;
	}

	public static void printAllPartitions()
	{
		BigInteger[] array = new BigInteger[size];
		for (int i = 0; i < size; i++)
		{
			array[i] = BigInteger.valueOf(0);
		}
		array[0] = BigInteger.valueOf(1);

		for (int i = 1; i < size; i++)
		{
			for (int j = 0; j + i < size; j++)
			{
				array[j + i] = array[j + i].add(array[j]);
			}
		}

		for (int i = start; i < size; i++)
		{
			System.out.println(i + " = " + array[i]);
		}
	}

	/**
	 * Количество разбиений на разлиные нечетные с длиной сравнимой с n по модулю 4
	 */
	public static void printShiftPartitions()
	{
		BigInteger[][][] array = new BigInteger[size + 2][size + 2][4];
		for (int i = 0; i < size + 2; i++)
		{
			for (int j = 0; j < size + 2; j++)
			{
				Arrays.fill(array[i][j], BigInteger.valueOf(0));
			}
		}
		for (int j = 0; j < size + 2; j++)
		{
			array[0][j][0] = BigInteger.valueOf(1);
			// Arrays.fill(array[0][j], BigInteger.valueOf(1));
		}

		for (int i = 1; i < size; i++)
		{
			for (int j = (i - 1) / 2 * 2 + 1; j >= 1; j -= 2)
			{
				for (int shift = 0; shift < 4; shift++)
				{
					array[i][j][shift] = array[i - j][j + 2][(shift + 1 - j + 4 * i) % 4].add(array[i][j + 2][shift]);
				}
			}
		}

		for (int i = 1; i < size; i += 1)
		{
			System.out.println(i + " = " + array[i][1][0]);
		}
	}

	public static void print2KPartitions()
	{
		BigInteger[][] array = new BigInteger[size][size];
		for (int i = 0; i < size; i++)
		{
			Arrays.fill(array[i], BigInteger.valueOf(i == 0 ? 1 : 0));
		}
		array[1][1] = BigInteger.ONE;

		for (int i = 1; i < size; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				if (i - 2 * j > 0)
					array[i][j] = array[i][j].add(array[i - 2 * j][j]);

				if (i - 2 * j + 1 > 0)
					array[i][j] = array[i][j].add(array[i - 2 * j + 1][j - 1]);
			}
			if (i % 100 == 0)
				System.out.println(i);
		}

		for (int i = 100; i < size; i += 100)
		{
			BigInteger sum = BigInteger.ZERO;
			for (int j = i % 4; j <= i; j += 4)
				sum = sum.add(array[i][j]);
			System.out.println(i + " = " + sum);
		}
	}

	/**
	 * Печатает количество разбиений на различные нечетные числа
	 */
	public static void printDiffOddPartitions()
	{
		BigInteger[] array = new BigInteger[size];
		for (int i = 0; i < size; i++)
		{
			array[i] = BigInteger.valueOf(0);
		}
		array[0] = BigInteger.valueOf(1);

		for (int i = 1; i < size; i += 2)
		{
			for (int j = size - i - 1; j >= 0; j--)
			{
				array[j + i] = array[j + i].add(array[j]);
			}
		}

		for (int i = 1; i < size; i += 1)
		{
			System.out.println(i + " = " + array[i]);
		}
	}

	public static void diffOddByDevisors()
	{
		BigInteger[] array = new BigInteger[size];
		Arrays.fill(array, BigInteger.ZERO);
		array[0] = array[1] = BigInteger.ONE;

		for (int i = 2; i < size; i++)
		{
			for (int j = 1; j <= i; j++)
				array[i] = array[i].add(array[i - j].multiply(BigInteger.valueOf(getSumOddDivisors(j))));
			array[i] = array[i].divide(BigInteger.valueOf(i));
		}

		for (int i = start; i < size; i++)
			System.out.println(i + " = " + array[i]);
	}

	private static int getSumOddDivisors(int i)
	{
		int result = 0;
		for (int j = 1; j <= i; j += 2)
		{
			if (i % j != 0)
				continue;
			result += j * (((i / j + 1) % 2 == 0) ? 1 : -1);
		}
		return result;
	}

	public static void ranksByFormula()
	{
		for (int i = 100; i < size; i += 100)
		{
			System.out.println(i + "  = " + getAsymptoticRank(i));
		}
	}

	public static double getAsymptoticRank(int number)
	{
		double vv1 = Math.pow(Math.E, Math.PI * Math.sqrt((number - 1.0 / 24) / 6.0));
		double vv2 = 4 * Math.pow(24.0 * number * number * number, 0.25);
		return vv1 / vv2;
	}
}